package leetcode.new_wrold;


public class T33 {
    int n;
    public int search(int[] nums, int target) {
        n = nums.length-1;
        if (target>nums[n] && target<nums[0]){
            return -1;
        }
        return BinarySearch(0,n,target,nums);
    }

    public int BinarySearch(int l,int r,int target,int[] nums){
        System.out.println("l="+l+",r="+r);
        if (l>r){
            return -1;
        }
        if (target>nums[r]&&target<nums[l]){
            return -1;
        }

        int mid = (l+r)/2;
        if (nums[mid]==target){
            return mid;
        }
        if (nums[l]==target){
            return l;
        }
        if (nums[r]==target){
            return r;
        }

        if (nums[mid]<nums[r]){
            if (target>nums[mid] && target<nums[r]){
                return BinarySearch(mid+1,r,target,nums);
            }
            return BinarySearch(l,mid,target,nums);
        }else {
            if (target<nums[mid] && target>nums[l]){
                return BinarySearch(l,mid,target,nums);
            }
            return BinarySearch(mid+1,r,target,nums);
        }
    }

    public static void main(String[] args) {
        T33 t33 = new T33();
        int res = t33.search(new int[]{4,5,6,7,8,1,2,3}, 8);
        System.out.println(res);
    }
}
